import java.util.Arrays;
import java.util.Stack;

public class Main {
    public static boolean validateStackSequences(int[] pushed, int[] popped) {
        Stack<Integer> stack1=new Stack<>();
        Stack<Integer> stack2=new Stack<>();
        for(int i=popped.length-1;i>=0;i--){
            stack2.push(popped[i]);
        }
        int i=0;
        while(i<pushed.length){
            stack1.push(pushed[i]);
            i++;
            while(!(stack1.empty()||stack2.empty())&&stack1.peek()==stack2.peek()){
                stack1.pop();
                stack2.pop();
                if(stack2.empty()) return true;
            }

        }
        return false;
    }
    public static String decodeString(String _s) {
        Stack<StringBuilder> ss=new Stack<>();
        ss.push(new StringBuilder());
        Stack<Integer> nums=new Stack<>();
        char[] s=_s.toCharArray();
        int i=0;
        while(i<s.length){
            if(s[i]>='0'&&s[i]<='9') {
                int tmp=0;
                while(s[i]>='0'&&s[i]<='9'){
                    tmp=tmp*10+(s[i]-'0');
                    i++;
                }
                nums.push(tmp);
            }
            else if(s[i]=='['){
                i++;
                StringBuilder tmp=new StringBuilder();
                while(s[i]>='a'&&s[i]<='z'){
                    tmp.append(s[i]);
                    i++;
                }
                ss.push(tmp);
            }
            else if(s[i]==']'){
                String tmp="";
                int t=nums.pop();
                for(int j=0;j<t;j++){
                    tmp=tmp+ss.peek().toString();
                }
                ss.pop();
                ss.peek().append(tmp);
                i++;
            }
            else if(s[i]>='a'&&s[i]<='z') {
                ss.peek().append(s[i]);
                i++;
            }
        }
        return ss.pop().toString();
    }

    public static int calculate(String _s) {
        Stack<Integer> sk=new Stack<>();
        char symbol='+';
        char[] s=_s.toCharArray();
        for(int i=0;i<s.length;i++){
            if(s[i]>='0'&&s[i]<='9'){
                int num=0;
                while(i<s.length&&s[i]>='0'&&s[i]<='9'){
                    num=num*10+(s[i]-'0');
                    i++;
                }
                if(symbol=='+'||symbol=='-') sk.push(num);
                else{
                    if(symbol=='*')
                        sk.push(sk.pop()*num);
                    else sk.push(sk.pop()/num);
                }
            }
            if(i<s.length&&(s[i]=='+'||s[i]=='-'||s[i]=='*'||s[i]=='/')) symbol=s[i];
        }
        int ret=0;
        while(!sk.empty()){
            ret+=sk.pop();
        }
        return ret;
    }
    public static boolean backspaceCompare(String s, String t) {
        Stack<Character> s1=new Stack<>();
        Stack<Character> s2=new Stack<>();
        int i=0;
        while(i<s.length()||i<t.length()){
            if(i<s.length()&&s.charAt(i)=='#'&&s1.size()>0) s1.pop();
            else{
                if(i<s.length())
                s1.push(s.charAt(i));
            }
            if(i<t.length()&&t.charAt(i)=='#'&&s2.size()>0) s2.pop();
            else {
                if(i<t.length())
                s2.push(t.charAt(i));
            }
            i++;
        }
        return  s1.toString().equals(s2.toString());
    }
    public static String removeDuplicates(String s) {
        if(s.length()<2) return s;
        StringBuilder ret=new StringBuilder();
        char[] ss=s.toCharArray();
        ret.append(ss[0]);
        for(int i=1;i<ss.length;i++){
            if(ret.length()!=0&&ret.charAt(ret.length()-1)==ss[i]){
                ret.deleteCharAt(ret.length()-1);
            }
            else ret.append(ss[i]);
        }
        return ret.toString();
    }
    public static void main(String[] args) {
        Stack<Integer> stack=new Stack<>();
        Stack<Integer> stack1=new Stack<>();
        //stack.push(1);
//        System.out.println(stack.toString().equals(stack1.toString()));
//        System.out.println(removeDuplicates("abbaca"));
//        System.out.println(backspaceCompare("y#fo##f","y#f#o##f"));
//        System.out.println(calculate("0-2147483647"));
//        System.out.println(decodeString("100[leetcode]"));
        int[] nums1={1,0};
        int[] nums2={1,0};
        System.out.println(validateStackSequences(nums1,nums2));
    }
}
